package algorithm.leetcode;

public class PackageProblem {

    /**
     * 时间复杂度和空间复杂度O(n*m),其中n为背包容量,m为物品数
     * @param weight 物品重量数组
     * @param value 物品价值数组
     * @param W 背包容量
     * @return
     */
    public int maxValue(int[] weight, int[] value, int W) {
        int n = weight.length;
        if (n == 0) return 0;

        int[][] dp = new int[n][W + 1];
        // 先初始化第 0 行，也就是尝试把 0 号物品放入容量为 k 的背包中
        for (int k = 1; k <= W; k++) {
            if (k >= weight[0]) dp[0][k] = value[0];
            else dp[0][k] = 0; // 这一步其实没必要写，因为dp[][]数组默认就是0
        }
        for (int i = 1; i < n; i++) {
            for (int k = 1; k <= W; k++) {
                // 存放 i 号物品（前提是放得下这件物品）
                int valueWith_i = (k-weight[i] >= 0) ? (value[i] + dp[i-1][k-weight[i]]) : 0;
                // 不存放 i 号物品
                int valueWithout_i = dp[i-1][k];
                dp[i][k] = Math.max(valueWith_i, valueWithout_i);
            }
        }
        return dp[n-1][W];
    }

    public int maxValueImproved(int[] weight, int[] value, int W) {
        int n = weight.length;
        if (n == 0) return 0;
        // 辅助空间只需要O(W)即可
        int[] dp = new int[W + 1];
        for (int i = 0; i < n; i++) {
            // 注意这里必须从后向前！！！
            for (int k = W; k >= 1; k--) {
                int valueWith_i = (k - weight[i] >= 0) ? (dp[k - weight[i]] + value[i]) : 0;
                int valueWithout_i = dp[k];
                dp[k] = Math.max(valueWith_i, valueWithout_i);
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        int[] weight = new int[]{1,2,3,5};
        int[] value = new int[]{1,3,4,7};
        PackageProblem pp = new PackageProblem();
        System.out.println(pp.maxValue(weight, value, 8));
    }

}
